\documentclass[12pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[spanish]{babel}
\usepackage{amsfonts}
\usepackage{algorithm2e}
\usepackage{listings}

\lstset{ %
			language=Python,
			basicstyle=\footnotesize,
			numbers=left,
			stepnumber=1,
			numbersep=4pt,
			tabsize=2,
}


\title{Problema de control de inventario}
\author{
        Ignacio Garay \\
                \and
        Ariel Liguori\\
        	\and
	Pablo Musumeci
}
\date{\today}



\begin{document}
\maketitle

\begin{abstract}
El presente es un an\'alisis sobre el problema de control de inventario con una aplicaci\'on de programaci\'on din\'amica.
\end{abstract}

\newpage
\tableofcontents
\newpage

\section{Introducci\'on}\label{intro}
El problema del control de inventario consta del problema que afronta 
una empresa para decidir en qu\'e momento ser\'ia \'optimo hacer el
pedido de compras tal que se cubra la demanda y se minimice el costo.
Debido a que es un problema que involucra un avance temporal, en el presente
se tomar\'a la hip\'otesis de que el tiempo es discretizable en alg\'un per\'iodo.
En nuestro caso, el problema ser\'a cuantizable en meses y el per\'iodo adoptado es el
de un a\~no.\\

\newpage
\section{Planteo}\label{planteo}
El planteo matem\'atico del problema es el siguiente:

La concesionaria tiene una cantidad $k$ de per\'iodos, en donde puede comprar una
cantidad $x_k$ de camiones. Se cuenta con un almacen en donde puede guardar camiones, 
lo cual modelizamos mediante la variable $x_k$ la cual representa la cantidad de
camiones que hay en el almacen en el per\'iodo k.

Existe una demanda la cual debemos cumplir, para eso debemos contar con esa cantidad
de camiones disponibles en ese per\'iodo (por disponibles nos referimos a la suma
de la cantidad de camiones en el almacen más la cantidad adquirida en dicho per\'iodo).
La cantidad de camiones que se puede guardar esta limitada por la capacidad 
del almacen, esto se ve reflejado en la siguiente ecuaci\'on:

\begin{equation}\label{..} x_k \le S\end{equation}

Se define el stock de cada mes como:

\begin{equation}\label{..} x_{k+1} = x_{k} + u_k - w_k \end{equation}

En donde $u_k$ representa la cantidad de camiones comprados, y $w_k$ la demanda
que se debe cumplir, ambas cantidades relacionadas a un per\'iodo $k$ en particular.\\

Almacenar un cami\'on en el dep\'osito tiene un costo asociado de valor $C$; mientras
que por cada orden de compra librada, tenemos un costo fijo (es decir, independiente
de la cantidad de camiones que se adquieran en dicha orden) a pagar.\\

El objetivo del algoritmo a desarrollar involucra determinar la \emph{asignaci\'on}
\'optima de la cantidad de camiones a comprar en cada mes, tal que se minizimen los
costos involucrados en las compras y almacenamiento de camiones; teniendo en cuenta
las restricciones propias del problema, como el límite de camiones que pueden estar
en el almacen.\\

El problema consiste en minimizar el costo de los pedidos en orden de
satisfacer una demanda especificada para cada per\'iodo de tiempo.
Estos per\'iodos se discretizan en meses $t_0 \leq t_1 \leq .. \leq t_{N-1}$.
Utilizamos las variables $x_k, u_k$ y $w_k$ para representar el stock
disponible, la cantidad de camiones a pedir, y la demanda en el per\'iodo
$t_k$. 

El stock evoluciona seg\'un la siguiente ecuacion:

$x_{k+1} = x_k + u_k - w_k \quad 0 \leq k \leq N - 1$
El costo en un periodo $t_k$ esta asociado al costo de mantener un camion en el 
almacen $C$, y el costo de expedir una \'orden de compra el cual es fijo e independiente
de la cantidad de camiones que se pida, y vale $K$.

El costo total se calcula como:

$ \sum_{k=0}^{N-1} C \times u_k + Y_k \times S $

en donde $Y_k$ vale 1 si se compra al menos un cami\'on, y 0 en otros casos.
 
Nuestro objetivo es minimizar dicho costo total.

\section{Algoritmo por programaci\'on din\'amica}\label{algoritmo}
\begin{algorithm}[H]

	\SetAlgoLined

	\KwData{$W$, $k$, $stock_{max}$, $c_{stock}$, $c_{compra}$ }
	\KwResult{$U$, $costo_{total}$ }
	$U\leftarrow lista\ con\ k+1\ ceros$\;
	$X\leftarrow lista\ con\ k+1\ ceros$\;
	$costo\leftarrow c_{compra}$\;
	$U[0] \leftarrow W[0]$\;
	$lastbuy\leftarrow 0$\;
	\For{i en $[1..k$)}{
		$dif \leftarrow W[i] - X[i]$\;
		\If{$dif > 0$}{
			\eIf{$c_{compra} > dif * c_{stock} * (lastbuy + 1)\ y\ (dif + X[lastbuy] \leq stock_{max})$}{
				$costo \leftarrow costo + dif * c_{stock}$\;
				$U[lastbuy] \leftarrow U[lastbuy] + dif$\;
				\For{$i\ en\ [lastbuy,k]$}{
					$X[i] \leftarrow  X[i] + dif$\;
				}
			}{
				$costo \leftarrow costo + c_{compra}$\;
				$lastbuy \leftarrow k$\;
				$U[k] \leftarrow dif$\;
			}
		}
		$X[k+1] \leftarrow X[k] + U[k] - W[k]$\;
	}
	$return\ U,\ costo$\;

\caption{Algoritmo de inventario por programaci\'on din\'amica}
\end{algorithm}

\newpage

\section{Análisis}\label{analisisdina}
La estrategia encarada para resolver el problema de inventario fue la de
programación dinámica. Esto es así debido a que el problema presenta
dos características fundamentales:
\begin{itemize}
	\item Subestructuras de soluciones.
	\item Solapamiento.
\end{itemize}
Es decir, nuestro problema se puede escribir como una \emph{combinación lineal}
de las subsoluciones óptimas de los subproblemas que lo conformen.
Esto se puede ver en la forma en la que se toman las decisiones en nuestro algoritmo.
El criterio de decisión es óptimo porque está basado en el principio de
optimalidad de Bellman.\\
Entonces, basados en que nuestro caso base es el que compro todo lo que voy a vender, por inducci\'on
podemos llegar al caso óptimo de la solución. Es interesante ver que,
si bien el problema del inventario puede plantearse para costos según k períodos,
en el algoritmo se tomó la simplificación de llevar el costo total, dado que
el problema no requería de una vista de los costos mensuales. A su vez, es importante
destacar el \'orden del algoritmo. Como se puede apreciar en el pseudocódigo, nuestro
peor caso de ejecución va a ser en el que compre elementos todos los meses. Si esto llegara
a suceder, estaría ejecutando con una cota máxima de $k^2$ operaciones. Debido a que ésta es
la entrada, entonces el órden algorítmico será $O(n^2)$, siendo $n$ la cantidad de períodos.
\newpage
\bibliographystyle{abbrv}
\bibliography{simple}

\newpage
\section{Anexo: implementaci\'on del algoritmo en Python}\label{codigo}
\subsection{inventory.py}
\lstinputlisting{inventory.py}
\newpage
\end{document}
